Content playback devices have become increasingly commonplace and allow for playback of a variety of different audio and/or video content. Such devices can oftentimes store large amounts of content that the user can select for playback. Rather than playing back the content in a specific order requested by the user, these devices can also provide a shuffle playback option that randomly selects the order for content playback. Unfortunately, current shuffle playback options oftentimes generate an ordering that does not appear sufficiently random to the user of the device and/or is otherwise not enjoyable to the user of the device. This, in turn, can lead to user frustration and annoyance with the device.